package cn.initcap.algorithm.leetcode;

// 这里是为了和leetcode保持一直，使用import*项目中不会这样使用
import java.util.*;

/**
 * 时间煮酒，代码写诗！
 * 专注问题建模能力，化繁为简，将大问题分割成一个一个小的问题，所有的问题都应该透过表象看本质！
 * 注意整型溢出问题、边界条件、空参数等问题!
 * 位运算符  （& | ^）
 * 快慢指针  （判断链表是否有环）
 * 指针对撞  （适合有序的数组）
 * 滑动窗口  （适合有序的数组）
 * 回溯剪枝  （递归回溯重要的优化思路）
 * 动态规划  （自底向上解决问题，用于递归的优化）
 * 记忆搜索  （自顶向下解决问题，用于递归的优化）
 * 状态压缩  （用于减少内存的浪费，如二维数组 转化 一维数组 ，用数的二进制标志true false Integer 最多可以标志32位）
 * floodfill（解决无向图问题思路，分四联通、八联通 等等也有可能不仅仅是方向）
 * 图论算法解决问题 eg: 279完全平方问题
 * 数据结构 数组、堆、栈、单调栈、队列、单调队列、位图、并查集、最小索引堆、AVL树、红黑树、哈希表、字典树、线段树
 * Java: Queue、PriorityQueue、List、Set .floor .ceiling、TreeMap .floorKey .ceilingKey、HashMap、LinkedHashMap
 * <p>
 * <p>
 * 测试链表程序
 * int[] arr = new int[]{1,2,3,4,5,6,7};
 * LinkedUtil.printLinkedList(reverseList(LinkedUtil.create(arr)));
 * <p>
 * <p>
 * 测试树结构程序
 * TreeNodeBuildUtil.buildTree(new Integer[]{1,2,3,null,5})
 *
 * @author initcap
 * @date Created in 2020/1/8 14:17.
 */
public class Solution {

    public static void main(String[] args) {
    }

    /**
     * 寻路方向四方向
     */
    private static int[][] d = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    /**
     * 寻路方向八方向
     */
    private static int[][] di = new int[][]{{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
    /**
     * 寻路矩阵尺寸
     */
    private static int m, n;
    /**
     * 访问标记
     */
    private static boolean[][] visited;
    private int count;
    private int start;
    private int end;
    private int res;

    /**
     * 单调队列解题 滑动窗口最大值问题
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) {
            return new int[0];
        }
        int[] res = new int[nums.length - (k - 1)];
        HumdrumQueue humdrumQueue = new HumdrumQueue(k);
        for (int i = 0; i < nums.length; i++) {
            if (i < k - 1) {
                // 先填满窗口前k - 1个元素
                humdrumQueue.push(nums[i]);
            } else {
                // 滑动走起
                humdrumQueue.push(nums[i]);
                res[i - (k - 1)] = humdrumQueue.max();
                humdrumQueue.pop(nums[i - k + 1]);
            }
        }
        return res;
    }

    /**
     * 单调栈解题 接雨水问题
     * int[] height = new int[]{0,1,0,2,1,0,1,3,2,1,2,1}
     * @param height
     * @return
     */
    public int trap(int[] height) {
        if (height == null) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int topIndex = stack.pop();
                // 将与当前相同的都移除
                while (!stack.isEmpty() && height[stack.peek()] == height[topIndex]) {
                    stack.pop();
                }
                // 相同的移除以后还有元素才需要进行计算
                if (!stack.isEmpty()) {
                    // 获取当前栈顶元素
                    int curTop = stack.peek();
                    res += (Math.min(height[curTop], height[i]) - height[topIndex]) * (i - curTop - 1);
                }
            }
            stack.add(i);
        }
        return res;
    }

    /**
     * 容器盛水问题
     *
     * @param x 第一个容器
     * @param y 第二个容器
     * @param z 想要得到的水量
     * @return
     */
    public static boolean canMeasureWater(int x, int y, int z) {
        if (x + y < z) {
            return false;
        }
        if (x == 0 || y == 0) {
            return z == 0 || x + y == z;
        }
        if (x + y == z) {
            return true;
        }
        Queue<Puzzle> queue = new LinkedList<>();
        Set<Puzzle> visited = new HashSet<>();

        queue.add(new Puzzle(0, 0));
        visited.add(new Puzzle(0, 0));
        while (!queue.isEmpty()) {
            Puzzle cur = queue.poll();

            // 存储所有下一步的可能
            Set<Puzzle> nexts = new HashSet<>(6);
            // 装满
            nexts.add(new Puzzle(x, cur.y));
            nexts.add(new Puzzle(cur.x, y));
            // 倒空
            nexts.add(new Puzzle(0, cur.y));
            nexts.add(new Puzzle(cur.x, 0));
            // 互相倒水
            int xval = Math.min(cur.x, y - cur.y);
            int yval = Math.min(x - cur.x, cur.y);
            nexts.add(new Puzzle(cur.x - xval, cur.y + xval));
            nexts.add(new Puzzle(cur.x + yval, cur.y - yval));

            for (Puzzle next : nexts) {
                if (!visited.contains(next)) {
                    queue.add(next);
                    visited.add(next);

                    if (next.x == z || next.y == z || next.x + next.y == z) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    /**
     * 使用异或 可以将数组中奇数个数的进行相加，偶数个的消除
     *
     * @param nums 数组
     * @return 奇数个的和
     */
    public static int singleNumber(int[] nums) {
        int ans = nums[0];
        if (nums.length > 1) {
            for (int i = 1; i < nums.length; i++) {
                ans = ans ^ nums[i];
            }
        }
        return ans;
    }

    public static int uniquePaths(int m, int n) {
        int[][] memo = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (i == 0) {
                for (int j = 0; j < n; j++) {
                    memo[i][j] = 1;
                }
            }
            memo[i][0] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                memo[i][j] = memo[i - 1][j] + memo[i][j - 1];
            }
        }
        return memo[m - 1][n - 1];
    }

    public static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] memo = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            memo[i] = 1;
        }
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    memo[i] = Math.max(memo[i], memo[j] + 1);
                }
            }
        }
        int max = 1;
        for (int i = 0; i < memo.length; i++) {
            max = Math.max(max, memo[i]);
        }
        return max;
    }

    public static int numIslands(char[][] grid) {
        int res = 0;
        m = grid.length;
        if (m == 0) {
            return res;
        }
        n = grid[0].length;
        visited = new boolean[m][n];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    res++;
                    floodfill(grid, i, j);
                }
            }
        }
        return res;
    }

    private static void floodfill(char[][] grid, int startx, int starty) {
        visited[startx][starty] = true;
        for (int i = 0; i < 4; i++) {
            int nex = startx + d[i][0];
            int ney = starty + d[i][1];
            if (inArea(nex, ney) && grid[nex][ney] == '1' && !visited[nex][ney]) {
                floodfill(grid, nex, ney);
            }
        }
    }

    private static boolean inArea(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    /**
     * 计算路径的和
     *
     * @param root 根节点
     * @param sum  和
     * @return
     */
    private static int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        int res = findSum(root, sum);
        if (root.left != null) {
            res += pathSum(root.left, sum);
        }
        if (root.right != null) {
            res += pathSum(root.right, sum);
        }
        return res;
    }

    private static int findSum(TreeNode node, int sum) {
        if (node == null) {
            return 0;
        }
        int res = 0;
        if (sum == node.val) {
            res += 1;
        }
        res += findSum(node.left, sum - node.val);
        res += findSum(node.right, sum - node.val);
        return res;
    }

    private static int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return sumNumbers(root, 0, root.val);
    }

    private static int sumNumbers(TreeNode root, int res, int cur) {
        if (root.left == null && root.right == null) {
            res += cur;
            return res;
        }
        if (root.left != null) {
            int n = cur * 10 + root.left.val;
            res = sumNumbers(root.left, res, n);
        }
        if (root.right != null) {
            int n = cur * 10 + root.right.val;
            res = sumNumbers(root.right, res, n);
        }
        return res;
    }

    /**
     * 打印所有到叶子节点的路径
     *
     * @param root
     * @return
     */
    private static List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList();
        if (root == null) {
            return res;
        }
        if (root.left == null && root.right == null) {
            res.add(root.val + "");
            return res;
        }

        List<String> leftList = binaryTreePaths(root.left);
        for (int i = 0; i < leftList.size(); i++) {
            res.add(root.val + "->" + leftList.get(i));
        }

        List<String> rightList = binaryTreePaths(root.right);
        for (int i = 0; i < rightList.size(); i++) {
            res.add(root.val + "->" + rightList.get(i));
        }

        return res;
    }

    public static int numSquares(int n) {
        // 采用有向无权图的思路进行解题，对数据进行建模
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(n, 0));

        // 使用标记法防止寻路是走重复的路径(0为未访问过节点，1为访问过节点)
        int[] visited = new int[n];

        // 对有向图采用广度优先遍历，将最短路径返回
        while (!queue.isEmpty()) {
            Node cur = queue.remove();
            int num = cur.num;
            int step = cur.step;

            for (int i = 1; num - i * i >= 0; i++) {
                int next = num - i * i;
                if (next < 0) {
                    break;
                }
                if (next == 0) {
                    return step + 1;
                }
                // 没访问的节点才放入队列
                if (visited[next] == 0) {
                    queue.add(new Node(next, step + 1));
                    visited[next] = 1;
                }
            }
        }
        return 0;
    }

    /**
     * 不同路径
     *
     * @param grid 数组
     * @return
     */
    public int uniquePathsIII(int[][] grid) {
        m = grid.length;
        if (m == 0) {
            return 0;
        }
        n = grid[0].length;
        this.count = 0;
        visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    count++;
                }
                if (grid[i][j] == 1) {
                    // 压缩
                    start = i * n + j;
                }
                if (grid[i][j] == 2) {
                    end = i * n + j;
                }
            }
        }
        dfs(grid, start, count + 2);
        return res;
    }

    private void dfs(int[][] grid, int v, int count) {
        int x = v / n;
        int y = v % n;
        visited[x][y] = true;
        count--;
        if (count == 0 && v == end) {
            visited[x][y] = false;
            res++;
            return;
        }
        for (int i = 0; i < d.length; i++) {
            int nex = x + d[i][0];
            int ney = y + d[i][1];
            if (inArea(nex, ney) && !visited[nex][ney] && grid[nex][ney] != -1) {
                dfs(grid, nex * n + ney, count);
            }
        }
        visited[x][y] = false;

    }

    /**
     * 最短路径
     *
     * @param grid 邻接矩阵
     * @return 最短路径步数
     */
    public int shortestPathBinaryMatrix(int[][] grid) {
        m = grid.length;
        if (m == 0) {
            return 0;
        }
        n = grid[0].length;
        visited = new boolean[m][n];
        int[][] pathWeight = new int[m][n];
        if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) {
            return -1;
        }
        if (m == 1 && n == 1) {
            return 1;
        }

        // BFS 广度优先遍历，寻找无权图最短路径,(队列只能维护一个维度，所以下面，一维 二维相互转换)
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        visited[0][0] = true;
        pathWeight[0][0] = 1;
        while (!queue.isEmpty()) {
            // 将一维坐标转换为二维
            int cur = queue.remove();
            int curx = cur / n;
            int cury = cur % m;
            for (int i = 0; i < di.length; i++) {
                int nex = curx + di[i][0];
                int ney = cury + di[i][1];
                if (inArea(nex, ney) && !visited[nex][ney] && grid[nex][ney] == 0) {
                    // 将二维坐标转换
                    queue.add(nex * n + ney);
                    visited[nex][ney] = true;
                    pathWeight[nex][ney] = pathWeight[curx][cury] + 1;
                }

                if (nex == m - 1 && ney == n - 1) {
                    return pathWeight[nex][ney];
                }
            }
        }
        return -1;
    }

    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        visited = new boolean[m][n];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (searchWord(board, word, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 从board[startx][starty] 开始，寻找word[index...word.length())
     *
     * @param board
     * @param word
     * @param index
     * @param startx
     * @param starty
     * @return
     */
    private boolean searchWord(char[][] board, String word, int index, int startx, int starty) {
        if (index == word.length() - 1) {
            return board[startx][starty] == word.charAt(index);
        }

        if (board[startx][starty] == word.charAt(index)) {
            visited[startx][starty] = true;
            // 从startx, starty 出发，向四个方向寻找
            for (int i = 0; i < 4; i++) {
                int nex = startx + d[i][0];
                int ney = starty + d[i][1];
                if (inArea(nex, ney) && !visited[nex][ney] && searchWord(board, word, index + 1, nex, ney)) {
                    return true;
                }
            }
            visited[startx][starty] = false;
        }

        return false;
    }

    /**
     * 树的最大深度
     *
     * @param root
     * @return
     */
    private int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    /**
     * 树的最小深度
     *
     * @param root
     * @return
     */
    private int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null) {
            return minDepth(root.right) + 1;
        }
        if (root.right == null) {
            return minDepth(root.left) + 1;
        }
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }

    /**
     * 优先队列解题（优先队列默认最小堆）
     * 前K个频率高的元素
     *
     * @param nums 数组
     * @param k    排名
     * @return
     */
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new TreeMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }

        PriorityQueue<Freq> pq = new PriorityQueue<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (pq.size() < k) {
                pq.add(new Freq(entry.getKey(), entry.getValue()));
            } else if (entry.getValue() > pq.peek().freq) {
                pq.remove();
                pq.add(new Freq(entry.getKey(), entry.getValue()));
            }
        }
        LinkedList<Integer> res = new LinkedList<>();
        while (!pq.isEmpty()) {
            res.add(pq.remove().e);
        }
        return res;
    }

    static class Puzzle {
        public int x;
        public int y;

        public Puzzle(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Puzzle puzzle = (Puzzle) o;

            if (x != puzzle.x) return false;
            return y == puzzle.y;
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }
    }

    static class Node {
        /**
         * 数值
         */
        int num;
        /**
         * 走到0所需要的距离
         */
        int step;

        Node(int num, int step) {
            this.num = num;
            this.step = step;
        }
    }

    class Freq implements Comparable<Freq> {
        public int e, freq;

        public Freq(int e, int freq) {
            this.e = e;
            this.freq = freq;
        }

        @Override
        public int compareTo(Freq another) {
            if (this.freq < another.freq) {
                return -1;
            } else if (this.freq > another.freq) {
                return 1;
            } else {
                return 0;
            }
        }
    }

}
